package 数组;

import java.util.*;

/**
 * @author 会玩的洋洋
 * https://leetcode-cn.com/problems/3sum/
 */
public class _15_三数之和 {
    /**
     * 双指针 + 排序
     * 通过排序将数组中的内容进行从小到大排序
     * 然后通过两层for循环 遍历出来两个数  如果存在与前一个相同的数  则直接跳过
     * 没有  则进行下一步操作
     * 再用第三个和第二个数 相加  与  第一个数的相反数对比  如果有小于等于的数  则把third去传入下一部分
     * 如果不存在third了  则跳出第二个数的循环
     * 如果存在相等于target的数  则为目标三个数
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        int n = nums.length;
        Arrays.sort(nums);

        for (int first = 0; first < n; ++first) {
            // 判断是否与前一个相等  如果相等 则跳过
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }

            int third = n - 1;
            int target = -nums[first];

            for (int second = first + 1; second < n; ++second) {
                // 判断是否与前一个相等  如果相等 则跳过
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                // 遍历查询是否存在等于或小于target的值
                while (third > second && nums[third] + nums[second] > target) {
                    --third;
                }

                // 如果相等  则说明数组中已经没有相加为0的数了  直接break
                if (second == third) {
                    break;
                }

                if (nums[third] + nums[second] == target) {
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    ret.add(list);
                }
            }
        }

        return ret;
    }
}
